package com.hdu.hot100.oneDimensionalDp;
import java.util.*;

public class lc322 {

    class Solution {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            int max = Integer.MAX_VALUE;
            Arrays.fill(dp, max);
            dp[0] = 0;
            for (int coin : coins) {
                for (int j = coin; j <= amount; j++) {
                    if (dp[j - coin] != max) {
                        dp[j] = Math.min(dp[j], dp[j - coin] + 1);
                    }
                }
            }
            return dp[amount] == max ? -1 : dp[amount];
        }
    }
}
